#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct node
{
    //以整型数据为例
    int data;

    //指向相邻节点的双指针
    struct node * prev;
    struct node * next;
}node;

node * initList()
{
    node * head = malloc(sizeof(node));
    if(head != NULL)
    {
        head->prev = head;
        head->next = head;
    }
    return head;
}

//创建新节点
node * newNode(int data)
{
    //分配一个新节点的内存
    node *new = malloc(sizeof(node));

    if(new != NULL)
    {
        new->data = data;
        new->next = new;
        new->prev = new;
    }
    return new;
}

//判断链表是否为空
bool isEmpty(node *head)
{
    return head->next ==head;
}

//头插法
void insertHead(node *head,node *new)
{
    //2.
    new->prev = head;
    //3.
    new->next = head->next;
    //4.
    head->next = new;
    //5.
    new->next->prev = new;
}

//遍历链表
void show(node *head)
{
    for(node *p = head->next; p != head; p = p->next)
    {
        printf("%d\t",p->data);
    }
    printf("\n");
}

//尾插法
void insertTail(node *head,node *new)
{
    new->prev = head->prev;
    new->next = head;

    new->prev->next = new;
    head->prev = new;
}

//查找节点
node * findNode(node *head,int data)
{
    node *p;
    for(p = head->next;p != head;p=p->next)
    {
        if(p->data == data)
        {
            return p;
        }
    }
    return NULL;
}

//删除节点
node removeNode(node *p)
{
    
            //1.
            p->prev->next = p->next;
            //2.
            p->next->prev = p->prev;

            //3.
            p->prev = p;
            //4.
            p->next = p;
}

//向前遍历
void listForEachPre(node *head)
{
    if(isEmpty(head))
        return;
    for(node *tmp = head->prev;tmp != head;tmp = tmp->prev)
    {
        printf("%d\t",tmp->data);
    }
    printf("\n");
}

//向后遍历
void listForEach(node *head)
{
    if(isEmpty(head))
        return;
    for(node *tmp = head->next;tmp != head;tmp = tmp->next)
    {
        printf("%d\t",tmp->data);
    }
    printf("\n");
}

//销毁节点
node *destroy(node *head)
{
    node *p;
    for(p = head->next;p != head; p = head->next)
    {
        removeNode(p);
        free(p);
    }
    free(head);
    return NULL;
}

int main(void)
{
    //初始化一条带头节点的空链表
    node *head = initList();
    if(head)
        printf("初始化空链表成功!\n");
    else
     {
        perror("初始化空链表失败");
        exit(0);
     }

     //在链表头部插入一些节点
     for(int i = 1; i <= 5 ; i++)
     {
        //1.
        node * new = newNode(i);

        //2~5
        insertHead(head,new);
     }

     //输出元素5,4,3,2,1
     show(head);

     //在链表尾部插入一些节点
     for(int i = 1; i <= 5 ; i++)
     {
        //1.
        node * new = newNode(i);

        //2~5
        insertTail(head,new);
     }

     //输出元素1,2,3,4,5
     show(head); 

    //删除输入的数据在链表中的数值
    int n;
    while(1)
    {
        scanf("%d",&n);

        if(n == 0)
            break;

        node *p = findNode(head,n);
        if(p == NULL)
        {
            removeNode(p);
            free(p);
        }
        else
            printf("没有你要删除的节点\n");

        show(head);
    }   

    //向后输出每个节点
    listForEach(head);

    //向前输出每个节点
    listForEachPre(head);

    //销毁整条链表
    head = destroy(head);

}